The invention relates to the field of computer graphics processing. More specifically, the invention relates to detail-in-context presentations and the inversion of distortions in detail-in-context presentations.
Since the advent of video display terminals as the primary interface to the computer, making the best use of the available screen space has been a fundamental issue in user interface design. This issue has been referred to as the xe2x80x9cscreen real estate problemxe2x80x9d. The necessity for effective solutions to this problem is growing as the ability to produce and store visual information in great volumes is outstripping the rate at which display technology is advancing. One solution to the screen real estate problem is the use of detail-in-context presentation techniques. Detail-in-context presentations are useful for displaying large amounts of information on limited-size computer screens.
Now, in the detail-in-context discourse, differentiation is often made between the terms xe2x80x9crepresentationxe2x80x9d and xe2x80x9cpresentation xe2x80x9d. A representation is a formal system, or mapping, for specifying raw information or data that is stored in a computer or data processing system. For example, a digital map of a city is a representation of raw data including street names and the relative geographic location of streets and utilities. Such a representation may be displayed visually on computer screen or printed on paper. On the other hand, a presentation is a spatial organization of a given representation that is appropriate for the task at hand. Thus, a presentation of a representation organizes such things as the point of view and the relative emphasis of different parts or regions of the representation. For example, a digital map of a city may be presented with a work route magnified to reveal street names. Thus, detail-in-context presentations allow for magnification of a particular region of interest (the xe2x80x9cfocal regionxe2x80x9d) in a representation while preserving visibility of the surrounding representation. In other words, in detail-in-context presentations focal regions are presented with an increased level of detail without the removal of contextual information from the original representation. In general, a detail-in-context presentation may be considered as a distorted view (or distortion) of a portion of the original representation where the distortion is the result of the application of a xe2x80x9clensxe2x80x9d like distortion function to the original representation. For reference, a detailed review of various detail-in-context presentation techniques may be found in Carpendale""s A Framework for Elastic Presentation Space (Carpendale, Marianne S. T., A Framework for Elastic Presentation Space (Burnaby, British Columbia: Simon Fraser University, 1999)).
One shortcoming of the prior art detail-in-context presentation methods is their inability to effectively invert distortions in a detail-in-context presentation back to an original or undistorted presentation of the representation. The ability to perform such an inversion or inverse mapping would be of great value in extending the capabilities of detail-in-context presentations to applications such as image editing. For example, the editing of a focal region in a representation may be facilitated more easily in a distorted presentation rather than in an undistorted presentation.
The ability to perform an inverse mapping is also necessary for applications involving the subsequent distortion of a previously distorted presentation. In other words, inversion would allow a presentation system user to accurately position or reposition one Or more distortion producing xe2x80x9clensesxe2x80x9d within a given presentation that has already been distorted. Hence, the distorted presentation ultimately viewed by the user may be the end result of a series of distortion steps wherein the individual distortion steps are not known or are difficult to invert. In fact, the need for inversion arises whenever it is necessary to position a lens based on observed coordinates in the distorted presentation. This is so because the lens may be directly generated only from coordinate information in the undistorted presentation. As such, an inversion is necessary to produce the source coordinates for generating the lens.
Moreover, inversion provides a means to calculate real distances in an undistorted presentation based on locations within one or more lenses in a corresponding distorted presentation. For example, if a user wants to know the distance in the undistorted presentation between the focal points of two separate lenses in a corresponding distorted presentation of a map, such as the distance between a current location and a destination location, this distance can be computed via inversions of the focal points of these lenses. Several systems are known which provide techniques for converting distorted or warped three-dimensional (3D) images into corrected, undistorted, or dewarped two-dimensional (2D) images. In U.S. Pat. No. 6,005,611 (Gullichsen, et al.), a system is disclosed wherein a distorted image captured by a wide-angle or fisheye lens is corrected through the use of a specially generated polynomial transform function that maps points from the distorted image into rectangular points. A more complex transform function is described in U.S. Pat. No. 5,185,667 (Zimmerman). In U.S. Pat. No. 5,329,310 (Liljegem, et al.) a similar objective is achieved in the context of motion picture images through the use of multiple lens (camera and projector) transfer functions. The result being the ability to project an image, taken from a particular point of view, onto a screen, especially a curved wide angle screen, from a different point of view, to be viewed from the original point of view, without distortion. In U.S. Pat. No. 5,175,808 (Sayre), a method and apparatus for non-affine image warping is disclosed that uses displacement tables to represent the movement of each pixel from an original location in a source image to a new location in a warped destination image. Through these displacement tables and a resampling method, the need for inversion of the underlying transform equation that specify the distortion or warp is eliminated, Finally, in U.S. Pat. No. 4,985,849 (Hideaki), look-up tables are used in combination with the forward evaluation of the transform equation in order to avoid the step of transform equation inversion. However, none of these systems disclose a method and system for inverting distortions in a manner that is optimized for detail-in-context presentations.
A need therefore exists for a method and system that will allow for the effective inversion of distortions in detail-in-context presentations. Therefore, it is an object of the present invention to obviate or mitigate at least some of the above mentioned disadvantages.
The invention provides a method and system for the inversion of distortions in detail-in-context presentations. According to one aspect of the invention, a method is provided that allows a distortion in a detail-in-context presentation to be inverted. The method comprises the steps of locating a first approximation point in an undistorted surface for the inversion of a point in a distorted surface, determining if the approximation point is acceptable as an inversion of the point in the distorted surface, locating a next approximation point in the undistorted surface if the first approximation point is not acceptable, and repeating this process until an acceptable approximation point is located for the inversion of the point in the distorted surface. According to another aspect of the invention, the use of this method to obtain the distance between points on an undistorted surface from the relative distances between corresponding points on a plurality of distorted surfaces in a detail-in-context presentation is provided. According to another aspect of the invention, a data processing system is provided. This data processing system has stored therein data representing sequences of instructions which when executed cause the above-described method to be performed. The data processing system generally has an input device, a central processing unit, memory, and a display.